COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003	.hd206 FALL 1977
C00017 ENDMK
C⊗;
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.PAGE FRAME 56 HIGH 80 WIDE;
.evenleftborder ← oddleftborder ← 1000;
.area text lines 1 to 56;
.place text;
.
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.SKIP  
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.
.
.MACRO hw (NUMBER, DUEDATE) ⊂
.   BEGIN TURNON "←"  NOFILL
←PROBLEM SET  NUMBER
←Due  DUEDATE
.   TURNOFF END ⊃
.
.itemmac
.
.PORTION MAINPORTION
.
.hd206 FALL 1977
.skip
.hw 1, |October 11|
.
.bb General homework policy. 

	When the homework involves writing LISP functions, debug your functions
using LISP at LOTS. Prepare a file that contains for each function the 
following:
.nofill

			1) The external form of your function.
			2) A ⊗brief description of how it works and why.
			3) An internal form listing.
			4) Results from some representative sample runs.
.fill
List this file and turn it in.  Include also the name of the file where
the functions live.  (For grading purposes, in case something is not clear,
it is useful to try out a function on suitable test cases.)

	Solutions will be put up in a file on the <CS206> directory and
you will be able to list, read, or load and try them.   Late assignments
are discouraged and will not be accepted after the solutions appear.

.bb Assignment.
.item ← 0
.BEGIN INDENT 0,6

	Write the following LISP functions.

#. ⊗⊗foo u⊗  is a list consisting of the atomic elements of the list ⊗u 
followed by a list of the nonatomic elements of ⊗u preserving the order within
each group.  Thus

⊗⊗⊗foo[$$(A (B C) A B (D E))$] = $$(A A B (B C) (D E))$⊗

#. ⊗⊗prod[u, v]⊗ is the product of the polynomials ⊗u and ⊗v.  We consider
only polynomials in one variable, say ⊗x, and represent a polynomial as a list
of its coefficients in order of increasing powers of ⊗x.  Thus 
⊗⊗x%53%*+x+5⊗ is represented by $$(5 1 0 1)$.  

#. ⊗⊗locations[e, u]⊗ is a list of the locations where ⊗e occurs as a subexpression
of ⊗u.  A location is a list ⊗⊗l⊗=(β%41%*_..._β%4n%*) where each β%4i%* is $A or
$D and 
$$(Cβ%41%*R_..._(Cβ%4n%*R_⊗⊗u⊗)...)$ is the subexpression at location ⊗l in ⊗u.  
Thus 

⊗⊗⊗locations[$Y, $$(((X . Y) . Z) . X)$] = $$((D A A))$⊗

#. ⊗⊗commons x⊗ is a list of pairs.  The set of ⊗⊗car⊗'s of the pairs is the set of
subexpressions of the S-expression ⊗x that occur more than once in ⊗x and the 
⊗cdr of each pair
is a list of the locations where the ⊗car occurs. Thus 

⊗⊗⊗commons $$(((X . Y) . Z) . X)$ = $$((X . ((A A A) (D))))$⊗

.END